For the unsorted database search, the famous Grover algorithm^[1,2] achieves a quadratic speedup over classical algorithms. Afterwards many analyses, generalizations and variants have been investigated.^[3–25] Grover’s algorithm has been proven optimal.^[26–30] However, the Grover algorithm cannot apply to the case where the fraction λ of target items is completely unknown expect for a lower bound, because iterating too much will pass by the target states, that is the so-called soufflé problem.^[31]

For the case of unknown λ, there are mainly two quantum search methods. One is the fixed-point method.^[32,33] In Ref. [32], the final state gradually converges to the target states along with the iterations, avoiding “overcooking” the state. However, the algorithm loses the valuable quantum speedup of quantum search,^[33] which has also been proven asymptotically optimal.^[34,35]

Fortunately, Yoder et al.^[33] creatively reduces the “fixed point” to a bounded region of the target states, and claimed that the quadratic speedup over classical search is maintained consequently, which has gained many recognitions.^[36–38] For example, in Ref. [38], Dalzell et al. pointed out that: “it (Yoder’s algorithm) produces |E⟩ (the uniform superposition over all the target states) with fidelity at least in only time, thus exhibiting the quadratic speedup”, where ω is a known lower bound of the unknown λ. Note that, for consistency, in the following, λ₀ instead of ω will be used to denote the lower bound of λ.

However, as stated in Ref. [38], the complexity in the quantum query model^[39,40] of Yoder’s algorithm is in rather than , which is dependent on the lower bound λ₀ rather than λ. For example, if λ₀ = 1/N, while , then , while . As another example, if λ₀ = 1/N, while λ = (N − 1)/N, then , while . Therefore, we confirm that the order of query complexity of Yoder’s algorithm is in fact not really optimal (for a detailed complexity analysis of Yoder’s algorithm see Section 2).

Another method for the case of unknown λ is the trial-and-error method.^[27,41–43] In this regard, the original work was proposed by Boyer et al.,^[27] which trials Grover’s algorithm multiple times, where the number of iterations is randomly selected from an exponentially increasing interval along with the number of trials. This randomness enables the average success probability at each trial is always at least 1/4 after the algorithm reaches the critical stage, and a target item can thus be found with an expected number of Grover iterations no more than , but the algorithm is therefore referred to as a randomized application of Grover’s algorithm. Based on this randomized trial-and-error method, replacing the internal Grover’s algorithm^[1] by the partial diffusion algorithm^[44] or fixed-phase algorithm,^[42] Younes et al. proposed two different variants,^[41,42] but the number of iterations was not reduced (for details see Table 1 in Section 4).

In order to remove the randomness of trial-and-error algorithms, Okamoto et al.^[43] directly set the number of Grover iterations exponentially increasing along with the trials and thus obtained a simpler deterministic trial-and-error algorithm, where the success probability at each trial can often (but not always) be no less than 3/4. This allows the algorithm to find a target state also in the optimal scaling of quantum search. But this also results in more than 1 times iterations or queries than Boyer’s randomized algorithm.

In this paper, we expect to design the first quantum search algorithm that hybridizes the fixed-point method and the trial-and-error method for the case of unknown λ, to confirm that the fixed-point method can also actually achieve the real optimal query complexity by selecting the number of iterations under the trial-and-error method, and confirm that the number of queries of the deterministic trial-and-error quantum search algorithm can be closer to (and even the number of iterations can be fewer than) the randomized versions.

The paper is organized as follows. Section 2 provides an introduction of Yoder’s fixed-point quantum search algorithm as well as an analysis of the query complexity. Section 3 describes our hybrid quantum search algorithm of the fixed-point method and the trial-and-error method. Section 4 discusses the comparisons between the existing algorithms and the algorithm in this paper, which also gives a brief conclusion.

Yoder’s algorithm^[33] aims to overcome the loss of quadratic speedup in the original fixed-point quantum search^[32] and avoid the soufflé problem in the original Grover algorithm.^[1]

The initial state of Yoder’s algorithm is prepared by applying operator A to the state |0⟩, which can be written as 1 where A = H is the Hadamard transform, |α⟩ (|β⟩) represents the equal superposition of all target (nontarget) states, i.e., 2 3 where λ = M/N is the fraction of target items, and M is the number of target items in the database of size N.

Yoder’s algorithm performs on |ψ⟩ the following sequence of matched-multiphase Grover operations (referred to as Yoder’s sequence) 4 Here l denotes the number of iterations, is the generalized Grover iteration,^[45] ( ) is the selective phase shift, conditionally changing the phase of target states (zero state) by a factor of φ (ϕ), expressed as 5 6 and the phases {ϕ_j, φ_j: 1 ⩽ j ⩽ l} satisfy the following multiphase matching condition^[33] 7 where L = 2l + 1, , δ ∈ (0,1), and T_L(x) is the L^th Chebyshev polynomial of the first kind,^[46] defined as 8

The final state of Yoder’s algorithm can be expressed as 9 where P_L denotes the success probability, satisfying 10 and for a given L, P_L ⩾ 1 − δ² as long as 11

Then, for a given λ, to ensure the success probability no less than 1 − δ², based on Eq. (11), letting ω ⩽ λ, the following condition of L can be obtained,^[33] i.e., 12 which demonstrates the fixed-point property. However, in the case of unknown λ, L_min is unknown. For this, it is assumed that there exists a known lower bound λ₀ of λ.^[33] Then, from Eq. (11), letting ω ⩽ λ₀, it follows that 13 Note that L₀ is known, because λ₀ is known. Therefore, the query complexity of Yoder’s algorithm is actually in , rather than , which is independent on λ and not really optimal. For example, if the lower bound λ₀ = 1/N, while (i.e., ), then the order of query complexity of Yoder’s algorithm is , which is actually the same as that of classical search, i.e., , while the algorithm that achieves the real quadratic speedup over classical algorithms should be in .

As described in Section 2, choosing the number of iterations relying on the lower bound λ₀ of λ, results in the problem that query complexity of Yoder’s algorithm^[33] is not really optimal. In addition, as described in Ref. [43], the existing deterministic trial-and-error algorithm requires more than 1 times iterations than the randomized version,^[27] due to the success probability of the original Grover algorithm^[1] oscillates intensively about λ. We expect to handle these problems by hybridizing the fixed-point method with the trial-and-error method, that is, we trials Yoder’s sequence (defined by Eq. (4)) multiple times and exponentially increase the number of iterations. At this time, the condition Eq. (12) of λ, rather than Eq. (13) of λ₀, could be satisfied rapidly, and after that the success probability at each trial would always (not just often) be no less than a given value, due to the fixed-point property. In this way, we could expect that a target item would be found with the expected Oracle queries in the real optimal order, and fewer number of iterations than the existing trial-and-error algorithms could be cost. First, we give the following lemma.

Now, we are ready to describe the hybrid quantum search algorithm for the unknown λ (the corresponding flow diagram is shown in Fig. 1).

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. Flow diagram of the hybrid fixed-point and trail-and-error quantum search algorithm.

By virtue of Lemma 1, we can obtain the lower bound of the success probability P_Ls, i.e., 27 and further obtain the upper bound of the occurrence probability Q_s, i.e., 28 Then, based on Eqs. (21), (23)–(28) we can obtain 29 30 where we have assumed that c < δ⁻². Finally, from Eqs. (22), (28)–(30), and l_cri ≫ log_c l_cri ≫ 1 for λ ≪ 1 − δ², it follows that 31 and numerical calculation shows that 32 Therefore, the query complexity of our algorithm is in . In addition, we can see that δ = 0.5659 and c = 1.523 are just the optimal parameters minimizing the upper bound of the expected query complexity.

In this section, we first discuss the comparisons between our algorithm and the existing quantum search algorithms^{[27,32,33,41–43]} in the case of unknown λ and then give a brief conclusion. Table 1 lists the method, query complexity, and phase(s) of our algorithm and other algorithms. The main advantages of our algorithm are discussed in detail as follows.

Table 1.

Table 1.

Table 1. Detailed comparisons between our algorithm and other algorithms. . Algorithm Method Query complexity Phase(s) Grover[32] fixed-point O(ln(1/δ)/λ0)a, b π/3 Yoder et al.[33] fixed-point a, b ϕj, φj of Eq. (7) Boyer et al.[27] trail-and-error (randomized) π Younes et al.[41] trail-and-error (randomized)c π Younes[42] trail-and-error (randomized)d 1.91684π Okamoto et al.[43] trail-and-error (deterministic) π Pro. Alg. fixed-point + trail-and-error (deterministic) {ϕj, φj} of Eq. (7) a λ0 is the assumed known lower bound of the unknown fraction λ of target items in Refs. [32] and [33], and the obtained success probability is no less than 1 − δ2, where δ ∈ (0,1). b The number of Grover iterations is half of it. Note that in the derivation of query complexity, the viewpoint of Ref. [33] has been adopted, that is, one Grover iteration with arbitrary phases other than π contains two queries of the standard quantum Oracle with phase-π, defined by Eq. (33). c Different from Boyer’s algorithm, the internal Grover’s algorithm is replaced by the partial diffusion algorithm.[44] d The internal Grover’s algorithm is replaced by the (1.91684π) fixed-phase algorithm.[42]

Table 1. Detailed comparisons between our algorithm and other algorithms. .

Compared with the fixed-point quantum search algorithms,^[32,33] as shown in Eq. (31) our algorithm indeed reaches the optimal scaling for quantum search, i.e., , while, references [32] and [33] do not. Reasons are in the following: First, for the original fixed-point quantum search algorithm,^[32] to achieve a success probability no less than than 1 − δ² (δ ∈ (0,1)) for an unknown λ with a known lower bound λ₀, the number of required Oracle queries^[35] is in yielding the loss of quadratic speedup over classical exhaustive search, which is in O(1/λ). Second, as shown in Eq. (13), the query complexity of Yoder’s algorithm^[33] is in , which indeed achieves a quadratic speedup over the original fixed-point algorithm. However, for any λ⩾ λ₀, the same as Ref. [32], the least number of iterations of Yoder’s algorithm is fixed. For example, if λ₀ = 1/N, while λ = (N − 1)/N ≈ 1, then a target item could almost be found by performing the classical search once, but the complexity of Yoder’s algorithm is still in . Therefore, Yoder’s algorithm does not achieve the quadratic speedup over classical search. Note that, this advantage of our algorithm comes from the use of trial-and-error method.

Compared with the trial-and-error quantum search algorithms,^[27,41–43] first, with respect to the method, our algorithm does not contain randomness (i.e., random selection of the number of iterations), and enables the success probability always no less than an arbitrary given lower bound between 0 and 1 after the number of iterations exceeds the critical value (i.e., l_cri defined by Eq. (20)). While, the existing randomized trial-and-error algorithms^[27,41,42] rely on the randomness, and the existing deterministic trial-and-error algorithm^[43] can only makes the success probability often (but not always) no less than a lower bound, fixed at 3/4. Second, with respect to the query/iteration complexity, compared with the existing deterministic trial-and-error algorithm,^[43] our query complexity can be reduced by (8.378 − 5.643) / 8.378 ≈ 1/3. Although, the upper bound of query complexity of our algorithm displayed in Table 1 is slightly higher than Boyer’s randomized algorithm^[27] (about 5.643/4 ≈ 1.4 times), however, in the derivation of query complexity, we have adopted the viewpoint in Ref. [33] that one Grover iteration with arbitrary phases queries two standard quantum Oracle (denoted by ) with phase-π, which flips the ancilla qubit when the input is the target state, i.e., 33 Therefore, in fact, our algorithm has fewer number of iterations, about 1 − (5.643/2)/4 ≈ 30% can be saved than Ref. [27]. This advantage comes from the use of fixed-point method in our algorithm.

Finally, it is worth mentioning that, for the quantum Oracle with arbitrary phases (i.e., , defined by Eq. (5)), Yoder et al. designed a feasible quantum circuit, including two standard quantum Oracle with phase-π, which appears to show that the complexity of is twice that of . However, we have noticed that in many practical applications of quantum search, e.g., key search in classical cryptography,^[47–49] the satisfiability problem,^[50,51] quantum machine learning,^[52] etc., the design of the standard quantum Oracle contains a quantization (denoted by Q_f) of the classical Oracle and the corresponding un-computation step (denoted by ) which restores the ancillary qubits to their initial state,^[53] as shown in Fig. 2. Therefore, the complexity of is twice that of Q_f, also as pointed in Ref. [54]. What is more, based on this, we can find out that follow the circuit of in Ref. [33], as depicted in Fig. 2, the in the first and the Q_f in the second could be omitted because they offset each other ( ). Therefore, the complexity of quantum Oracle with arbitrary phases would also be twice that of Q_f, which is the same as that of the standard Oracle . In this case, our algorithm will has the least query complexity among the current algorithms for the unknown λ.^{[27,32,33,41–43]} While, this conclusion may be related to the specific application scenario of the algorithms, and more rigorous proofs can be studied further in the future.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. Circuit for the quantum Oracle with arbitrary phases, defined by Eq. (5), where denotes the quantum Oracle with phase-π (defined by Eq. (33)), Qf is the quantization of the classical Oracle, corresponds to the un-computation step to restore the ancillary qubits, and is the quantum gate adding a phase of eiφ to |1⟩ state.

In summary, we have presented the first quantum search algorithm hybridizing the fixed-point method with the trial-and-error method for the unknown λ, which integrates the advantages of both methods and solves the non-optimal problem of the “optimal” fixed-point algorithm^[33] and the problem that the deterministic trial-and-error algorithm^[43] requires more than 1 times queries or iterations than the randomized versions. In our algorithm, the Yoder’s sequence^[33] is conducted multiple trials, and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries of our algorithm to find a target item was derived, as well as the optimal parameters, which minimize the query complexity. Our study reconfirms the practicality of the fixed-point method, and shows that it is very advantageous to hybridize the trial-and-error method and the fixed-point method, which provides a different approach for the research on quantum search algorithms and can be applied to a variety of scenarios where Grover’s search is used.^[47–52]